package class07_加强堆.test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Code01_CoverMax {
    public static int maxCover1(int[][] line){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < line.length; i++) {
            min = Math.min(min, line[i][0]);
            max = Math.max(max, line[i][1]);
        }
        int cover = 0;
        for (double i = 0.5; i < max; i+=1) {
            int cur = 0;
            for (int j = 0; j < line.length; j++) {
                if(line[j][0] < i && line[j][1] > i){
                    cur++;
                }
            }
            cover= Math.max(cover, cur);
        }
        return cover;
    }
    public static int maxCover2(int[][] line){
        Line[] lines = new Line[line.length];
        for (int i = 0; i < line.length; i++) {
            lines[i] = new Line(line[i][0], line[i][1]);
        }
        Arrays.sort(lines,new StartComparator());

        PriorityQueue<Integer> queue = new PriorityQueue();
        int cover = 0;
        for (int i = 0; i < lines.length; i++) {
            while (!queue.isEmpty() && queue.peek() <= lines[i].start){
                queue.poll();
            }
            queue.add(lines[i].end);
            cover = Math.max(cover,queue.size());
        }
        return cover;
    }
    public static class Line{
        private int start;
        private int end;
        public Line(int s, int e){
            this.start = s;
            this.end = e;
        }
    }
    public static class StartComparator implements Comparator<Line> {

        @Override
        public int compare(Line o1, Line o2) {
            return o1.start - o2.start;
        }
    }

    public static void main(String[] args) {
        int testTimes = 50000;
        int N = 100;
        int L = 0;
        int R = 100;
        for (int i = 0; i < testTimes; i++) {
            int[][] arr = generateLines(N, L, R);
            int ans = maxCover1(arr);
            int ans2 = maxCover2(arr);
            if(ans != ans2){
                System.out.println("Oops!!");
            }
        }
        System.out.println("succeed!!!!");
    }

    private static int[][] generateLines(int n, int l, int r) {
        int size = (int)(Math.random() * n + 1);
        int[][] help = new int[size][2];
        for (int i = 0; i < size; i++) {
            int a = l + (int)(Math.random() * (r - l) + 1);
            int b = l + (int)(Math.random() * (r - l) + 1);
            if(a == b){
                a += 1;
            }
            help[i][0] = Math.min(a, b);
            help[i][1] = Math.max(a, b);
        }
        return help;
    }
}
